public class Main {
    // 演示三种常见排序算法：冒泡排序、快速排序、归并排序
    // 所有排序方法均对 int 数组进行「原地」升序排序，并在 main 方法中做简单演示。

    public static void main(String[] args) {
        // 准备多组测试用例，方便观察不同算法在不同输入下的表现
        int[] arrRandom = {5, 2, 9, 1, 5, 6};   // 一般无序数组
        int[] arrEmpty = new int[0];            // 空数组
        int[] arrSingle = {42};                 // 只有一个元素
        int[] arrSorted = {1, 2, 3, 4, 5};      // 已经有序
        int[] arrReversed = {5, 4, 3, 2, 1};    // 完全逆序

        // 说明：下面在调用每种排序算法前都会使用 clone() 复制数组，
        // 这样可以保证每个算法看到的初始输入是一致的，便于公平比较。

        System.out.println("===== 冒泡排序（Bubble Sort） =====");
        demoSort("冒泡排序", Main::bubbleSort, arrRandom, arrEmpty, arrSingle, arrSorted, arrReversed);

        System.out.println("\n===== 快速排序（Quick Sort） =====");
        demoSort("快速排序", Main::quickSort, arrRandom, arrEmpty, arrSingle, arrSorted, arrReversed);

        System.out.println("\n===== 归并排序（Merge Sort） =====");
        demoSort("归并排序", Main::mergeSort, arrRandom, arrEmpty, arrSingle, arrSorted, arrReversed);
    }

    /**
     * 通用的排序演示工具方法：
     * 接收一个排序算法（通过函数式接口 SortFunction 表示），
     * 对多组数组用例进行排序并打印前后结果。
     */
    private static void demoSort(String sortName, SortFunction sorter,
                                 int[] arrRandom, int[] arrEmpty, int[] arrSingle,
                                 int[] arrSorted, int[] arrReversed) {
        runCase(sortName + "-随机数组", sorter, arrRandom);
        runCase(sortName + "-空数组", sorter, arrEmpty);
        runCase(sortName + "-单元素数组", sorter, arrSingle);
        runCase(sortName + "-已排序数组", sorter, arrSorted);
        runCase(sortName + "-逆序数组", sorter, arrReversed);
    }

    /**
     * 对单个用例执行排序并打印排序前后的数组。
     */
    private static void runCase(String label, SortFunction sorter, int[] original) {
        int[] copy = original == null ? null : original.clone();
        System.out.println("-- " + label + " --");
        printArray("排序前", copy);
        sorter.sort(copy);
        printArray("排序后", copy);
        System.out.println();
    }

    /**
     * 辅助方法：格式化打印数组内容。
     * 对 null 或空数组进行特殊处理，避免空指针异常。
     */
    private static void printArray(String label, int[] arr) {
        if (arr == null) {
            System.out.println(label + ": null");
            return;
        }
        if (arr.length == 0) {
            System.out.println(label + ": [] (空数组)");
            return;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(label).append(": [");
        for (int i = 0; i < arr.length; i++) {
            if (i > 0) {
                sb.append(", ");
            }
            sb.append(arr[i]);
        }
        sb.append("]");
        System.out.println(sb.toString());
    }

    // ================== 冒泡排序 ==================

    /**
     * 冒泡排序（Bubble Sort）
     *
     * 核心思想：
     * - 多次遍历数组，每次比较相邻两个元素，如果前一个比后一个大，则交换它们。
     * - 一趟遍历结束后，当前未排序部分中最大的元素会“冒泡”到末尾。
     *
     * 时间复杂度：
     * - 最坏和平均情况：O(n^2)
     * - 最好情况（数组本身已经有序，且使用了提前结束优化）：O(n)
     * 空间复杂度：O(1)，只需要常数级额外空间。
     * 稳定性：稳定排序（相等元素不会交换相对位置）。
     *
     * 边界情况处理：
     * - 如果 arr 为 null，或长度小于等于 1，则不做任何操作，直接返回。
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        int n = arr.length;
        // 外层循环控制遍历的趟数
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false; // 标记本趟是否发生过交换
            // 内层循环实际比较的范围每趟都会减少，因为后面的元素已经排好序
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 相邻元素逆序，则交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果某一趟没有发生任何交换，说明数组已经有序，可以提前结束
            if (!swapped) {
                break;
            }
        }
    }

    // ================== 快速排序 ==================

    /**
     * 快速排序（Quick Sort）- 对外暴露的入口方法。
     *
     * 核心思想：分治（Divide and Conquer）：
     * - 从数组中选择一个“基准”（pivot），将数组分成两部分：
     *   左侧元素都不大于 pivot，右侧元素都不小于 pivot。
     * - 然后对左右两部分分别递归地进行同样的操作。
     *
     * 时间复杂度：
     * - 平均时间复杂度：O(n log n)
     * - 最坏时间复杂度：O(n^2)（例如数组已排序且每次选取两端元素为基准时容易出现）
     * 空间复杂度：
     * - 主要来自递归调用栈，平均为 O(log n)，最坏为 O(n)。
     * 稳定性：
     * - 非稳定排序（相等元素在分区交换的过程中可能改变相对顺序）。
     *
     * 边界情况处理：
     * - 如果 arr 为 null，或长度小于等于 1，则不做任何操作，直接返回。
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    // 递归实现快速排序，对区间 [left, right] 进行排序。
    private static void quickSort(int[] arr, int left, int right) {
        // 递归结束条件：区间内不足两个元素，已经有序
        if (left >= right) {
            return;
        }

        // 这里选择中间元素作为基准，通常能在随机数据下取得较好的表现，
        // 同时可以一定程度上避免在已有序/逆序数组上的最坏情况。
        int i = left;
        int j = right;
        int pivot = arr[left + (right - left) / 2];

        // 分区过程：将小于 pivot 的放在左边，大于 pivot 的放在右边
        while (i <= j) {
            // 从左侧找到第一个 >= pivot 的元素
            while (arr[i] < pivot) {
                i++;
            }
            // 从右侧找到第一个 <= pivot 的元素
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                // 交换左右两侧不在正确区间的元素
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        // 此时 [left, j] 区间内元素都不大于 pivot，
        // [i, right] 区间内元素都不小于 pivot，
        // 对这两个子区间分别递归排序。
        if (left < j) {
            quickSort(arr, left, j);
        }
        if (i < right) {
            quickSort(arr, i, right);
        }
    }

    // ================== 归并排序 ==================

    /**
     * 归并排序（Merge Sort）- 对外暴露的入口方法。
     *
     * 核心思想：分而治之 + 归并（Merge）：
     * - 不断将数组“二分”成更小的子数组，直到子数组的长度为 1（天然有序）。
     * - 然后将两个有序子数组“归并”成一个更大的有序数组。
     *
     * 时间复杂度：
     * - 无论最好、最坏还是平均情况，时间复杂度都为 O(n log n)。
     * 空间复杂度：
     * - 需要一个与原数组等长的临时数组存放中间结果，空间复杂度为 O(n)。
     * 稳定性：
     * - 稳定排序（在合并时如果遇到相等元素，优先拷贝左侧的元素即可保持稳定性）。
     *
     * 边界情况处理：
     * - 如果 arr 为 null，或长度小于等于 1，则不做任何操作，直接返回。
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length]; // 只申请一次临时数组，避免在递归中反复申请
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    // 递归对区间 [left, right] 进行归并排序
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left >= right) {
            // 当区间内只有一个元素或者没有元素时，已经是有序的
            return;
        }
        int mid = left + (right - left) / 2;
        // 递归排序左半部分 [left, mid]
        mergeSort(arr, left, mid, temp);
        // 递归排序右半部分 [mid + 1, right]
        mergeSort(arr, mid + 1, right, temp);
        // 将两个有序子数组归并为一个更大的有序数组
        merge(arr, left, mid, right, temp);
    }

    // 将 arr[left..mid] 和 arr[mid+1..right] 这两个有序区间归并到 temp 中，再拷贝回 arr
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;      // 指向左半部分的起始位置
        int j = mid + 1;   // 指向右半部分的起始位置
        int k = left;      // 指向临时数组的当前位置

        // 合并两个有序区间
        while (i <= mid && j <= right) {
            // 为了保持稳定性，当 arr[i] == arr[j] 时，优先拷贝左侧元素 arr[i]
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 将左半部分剩余元素拷贝到 temp
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 将右半部分剩余元素拷贝到 temp
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 最后将 temp 中 [left, right] 区间的结果拷贝回原数组
        for (int idx = left; idx <= right; idx++) {
            arr[idx] = temp[idx];
        }
    }

    // ================== 扩展说明 ==================

    /**
     * 扩展点（暂未实现，仅作为后续重构方向）：
     *
     * 1. 支持任意类型和自定义比较方式
     *    - 可以使用 Java 泛型和 Comparator，例如：
     *      <T> void sort(T[] arr, Comparator<T> cmp)
     *    - 排序算法的比较逻辑统一由 cmp 决定，可以复用本文中冒泡/快速/归并的整体结构。
     *
     * 2. 支持升序 / 降序开关
     *    - 方案 A：在方法中增加一个 boolean ascending 参数，根据该值决定比较方向
     *      （例如：ascending 为 false 时，将 "<" 改为 ">" 进行比较）。
     *    - 方案 B：在比较结果外层包一层判断，或在调 Comparator 时对返回值取反。
     *
     * 目前为演示起见，仅实现了对 int 数组的升序排序，方便理解核心算法思想。
     */
    private interface SortFunction {
        void sort(int[] arr);
    }
}